Problem statement: zenit11ckc

c) (20 bodov)

Pri prvom cvičnom zadaní si sa prejavil ako schopný programátor a preto je najvyšší čas zveriť ti nejakú naozaj zodpovednú úlohu. Táto úloha sa týka najvýznamnejšej športovej udalosti C-planéty. C-planéťania sú veľmi svojská civilizácia. Každosezónnym vyvrcholením diania na tejto planéte je pretek vesmírnych lodí. Vesmírne lode majú za čo najkratší čas preletieť určenú vzdialenosť, pričom cestovanie v čase je v priebehu súťaže zakázané. Keďže lodí na štarte je príliš veľa, pretekári boli rozdelení na 100 skupín. Skupiny štartujú v intervale niekoľkých intergalaktických minút. Keď do cieľa priletí účastník z neskoršej skupiny skôr ako účastník zo skoršej skupiny, voláme to prekvapením. Celkové prekvapenie preteku je počet dvojíc pretekárov, ktoré spôsobujú prekvapenie. Keď pretek skončí príliš prekvapujúcim výsledkom, tak celá spoločnosť C-civilizácie znervóznie, následkom čoho môže vzniknúť napríklad intergalaktická vojna. Napíšte program, ktorý prečíta výsledky pretekov a vypočíta jeho celkové prekvapenie. Vieme, že žiadni dvaja pretekári neprišli do cieľa naraz.

Na vstupe je na prvom riadku číslo N: počet pretekárov (1<=N<=100,000). Na ďalšom riadku vstupu je N medzerami oddelených čísel: štartovné skupiny pretekárov v poradí, v akom prichádzali do cieľa (všetky čísla sú medzi 1 a 100 vrátane). Napríklad čísla 3,1,2 znamenajú, že najprv prišiel do cieľa pretekár z tretej štartovnej skupiny, potom z prvej štartovnej skupiny a ako tretí prišiel pretekár z druhej štartovnej skupiny. Celkové prekvapenie tohto poradia je 2: pretekár z tretej skupiny predbehol niekoho z prvej skupiny a ten istý pretekár z tretej skupiny predbehol niekoho z druhej skupiny. Nemôžete predpokladať nič o delení pretekárov medzi štartovné skupiny: ani to, že sú skupiny rovnako veľké a dokonca ani to, že nejaká štartovná skupina je neprázdna.

Príklad:

Vstup:

5
4 3 6 1 2

Výstup:

7

Vstup:

7
10 25 30 30 70 100 25

Výstup:

4

Medzi skušobnými testovacími dátami sa nachádza aj jeden vstup (sample.02.in), kde N=100,000. Ten sme sa ale rozhodli do zadania neuvádzať :).